Various use cases exist for forming device-to-device communication networks such as wireless ad hoc networks or wireless mesh networks. For example a group of public safety personnel (police, firemen, etc.) may form a device-to-device communication group with the devices being geographically distributed such that forming direct communication links is not possible between any arbitrarily chosen set of devices. In other words, the devices could be out of radio coverage range of each other. By using an ad hoc networking or mesh-networking approach, data can be forwarded from a source device (i.e. source node) to one or more destination devices (i.e. destination nodes), through intermediate nodes in the network. In many cases the intermediate nodes that perform such data-forwarding operations may also be destination nodes and this further improves network efficiency. However, forwarding the data through intermediate nodes also implies that some network links can become bottlenecks. Some mesh networking approaches may involve using sophisticated routing algorithms running in the mesh network, but this approach requires maintenance and exchange of routing tables and does not fully alleviate the problem of bottleneck network links.
Network coding is an alternative to routing packets through a mesh network when transmitting data from one node to multiple nodes (i.e. in multicast transmission). Packet routing in a network consists of routers receiving packets on inbound connections, deciding which outbound links to forward those packets on and forwarding the packets. In contrast, for network coding, intermediate nodes take the place of routers and “mix” the inbound packets. This allows the intermediate nodes to transmit fewer mixed packets rather than many original packets. The destination nodes receive the mixed packets and decode the original packets. The mixing consists of computing combinations of incoming packets. For computational ease, linear combinations are used.
FIG. 1 illustrates a known approach to network coding as discussed by Rudolf Ahlswede, Ning Cai, Shuo-Yen, Robert Li and Raymond W. Yeung, “Network Information Flow,” IEEE Trans. Inf. Theory, vol. 46. no. 4. (July 2000). [hereinafter “Ahlswede, et al”]. In FIG. 1, a mesh network is represented by a graph 100 with seven nodes in which each edge of the graph 100 represents a communication link. Each edge or communication link is operative to transmit one packet in a given time slot. The goal of the mesh network is to deliver a set of packets from the first node (node 1) to the sixth and seventh nodes (node 6 and node 7) through intermediate nodes.
Given that node 1 has two outbound edges and both edges can lead to both destination node 6 and node 7, it is possible to transmit different packets on the two edges. FIG. 1(a) shows the transmission of packets P1 and P2 on the two edges 1→2 and 1→3. Packet P1 can thus be transmitted to node 6 and node 7 respectively via edges 2→6 and 3→7. Node 4 receives both packet P1 and packet P2. However, only one packet can be transmitted in a time slot on edge 4→5. This means that edge 4→5 is a bottleneck communication link in the mesh network.
Viewing the network shown if FIG. 1(a) as a pipeline for communication of packets from node 1 to node 6 and node 7, in a first time slot, node 6 may receive packet P1 via edge 2→6 and packet P2 via edge 5→6. However node 7 can then only receive one packet, P2, via edge 3→7 in the first time slot. In a second time slot node 6 will only receive only one packet, P1, via edge 2→6 while node 7 will receive packet P2 via edge 3→7 and packet P1 via edge 5→7. In other words, only 1.5 packets can be received on average at both node 6 and node 7, per time slot, due to the bottleneck created at edge 4→5 which can only transmit one packet per time slot.
FIG. 1(b) illustrates the network coding approach. As in FIG. 1(a) edges 1→2, 2→6 and 2→4 carry packet P1, and edges 1→3, 3→7 and 3→4 carry packet P2. However in this example, node 4 performs a linear combination of P1 and P2, and transmits the linear combination on edge 4→5. More particularly, the linear combination operations are performed in a Galois Field. In an example in which the packets P1 and P2 are binary digits (i.e. binary “0” or “1”), the linear combination is implemented as an exclusive-OR operation (“XOR”). The linearly combined packet, (i.e. XOR of P1, P2) is then transmitted on edges 5→6 and 5→7. Node 6 therefore receives both packet P1 and packet P1⊕P2. Because node 6 knows the contents of packet P1, it can recover packet P2 from P1⊕P2 by performing an XOR operation of packet P1 and packet P1⊕P2. Similarly node 7 receives packet P2 and packet P1⊕P2 and recovers packet P1 from packet P1⊕P2. In other words, the scheme illustrated in FIG. 1(b) enables node 6 and node 7 to each receive two packets per time slot.
The computation of a “linear network code” (also known as a Linear Code Multicast, or LCM) for multicasting packets from source devices to destination devices in an arbitrary network has been discussed extensively in the literature. The devices are considered to be network “nodes” where a source device or source node is designated as “s” and a destination device or destination node (also referred to as a “sink node”) is designated as “T”.
Thus, as a mathematically informal example to illustrate the concepts of network coding (i.e. without detailed discussion of vector spaces), given an arbitrary network with source nodes “s” and a set of sink nodes “T”, where the arbitrary network is defined by a directed graph G=(V, E, s, T) where V is the set of vertices, E⊂ V×V, is the set of edges, s is the source vertex and T is the set of sink nodes, then a linear network code or LCM for the network represented by the directed graph consists of:                i. a Galois field F;        ii. for each e ∈ E′, E′ ⊂ E an assignment of an “Encoding Vector” EV(e), over elements of F to each edge e ∈ E′, E′ ⊂ E; and        iii. for each t ∈ T, a “Global Transfer Matrix” GT(t).        
The following additional conditions need to be satisfied:                a) Lv(e), where e=x→y, has to be a linear combination of the elements of {Lv(e′)|e′ ∈E′, e′=u→x, u ∈ V}, i.e., a linear combination of the local encoding vectors for the inbound edges.        b) for each t ∈ T:                    i. GT(t) is an r×r matrix, where r is the minimum of number of edge-disjoint paths (i.e. distinct paths) from s to each t ∈ T;            ii. each row of GT(t) represents an encoding vector for one of the edge-disjoint paths from s to t; and            iii. GT(t) is a full rank matrix.                        
Given the definitions and requirements set forth above, multicast packet transmission from a source device “s” to each destination device “t”, where “t” represents one destination device as an element of the set of destination devices “T” (i.e. t ∈ T), consists of the following procedures. First, each intervening device between the source devices and the destination devices constructs at “local transfer matrix”. These intervening devices are referred to herein interchangeably as “vertices”, “vertex devices” or “nodes”. Source devices and destination devices are also referred to herein as “nodes” and are referred to as “source nodes” and “destination nodes,” respectively, when necessary for purposes of clarity. For example, turning to FIG. 2, a source device in a network graph 200 is represented by node 1, vertex devices are represented by nodes 2 through 6 and node 8, and destination devices are represented by node 7 and node 9.
Each vertex device (designated as a “node v”) constructs a local transfer matrix “Lv” using encoding vectors (EV) defined for the inbound graph edges directed to the vertex device, and encoding vectors defined for the outbound graph edges directed away from the vertex device. More particularly, the local transfer matrix Lv at a vertex device is determined based on the following relationship between the outbound graph edge encoding vectors and the inbound graph edge encoding vectors:
            [                                                  EV              ⁡                              (                                  o                  1                                )                                                                                        EV              ⁡                              (                                  o                  2                                )                                                                          ⋮                                                              EV              ⁡                              (                                  o                  m                                )                                                        ]        =                  L        v            ⁡              [                                                            EV                ⁡                                  (                                      i                    1                                    )                                                                                                        EV                ⁡                                  (                                      i                    2                                    )                                                                                        ⋮                                                                          EV                ⁡                                  (                                      i                    n                                    )                                                                    ]              ,where o1, o2, . . . , om ∈ E′ are outbound graph edges directed away from v and i1, i2, . . . im ∈ E′ are inbound graph edges directed to the vertex device v.
The local transfer matrix “Ls” for the source device is computed as the identity of the encoding vectors defined for the outbound graph edges directed away from the source device. In other words, Ls is computed based on the following relationship:
            [                                                  EV              ⁡                              (                                  o                  1                                )                                                                                        EV              ⁡                              (                                  o                  2                                )                                                                          ⋮                                                              EV              ⁡                              (                                  o                  m                                )                                                        ]        =                  L        s            ⁢              I        r              ,      where    ⁢                  ⁢          I      r        ⁢                  ⁢    is    ⁢                  ⁢    the    ⁢                  ⁢    r    ×    r    ⁢                  ⁢    identity    ⁢                  ⁢          matrix      .      
For packet transmission, the source device s constructs “r” packet data fragments designated as [p1, p2, . . . , pr] such that each data fragment p1 is an element of an alphabet subset. At the source device (i.e. source node s), outgoing packet data fragments Pout(s)=[pout1(s), pout2(s), . . . , poutn(s)] on outbound edges are computed using the source local transfer matrix Ls such that: Pout(s)T=Ls[p1, p2, . . . , pr]T.
At each subsequent network node (designated as “u”), once packet data fragments on all inbound edges are received, the packet data fragments for the outbound edges are computed. If Pin(u)=[pin1(u), pin2(u), . . . , pinn(u)] are the packet data fragments received on the inbound edges to network node u, and Pout(u)=[pout1(u), pout2(u), . . . , poutn(u)] are the packet data fragments to transmit on the outbound edges from network node u, then Pout(u)T=LuPin(u)T.
At each destination device, once the packet: data fragments Pin(t) on all the inbound edges are received, the original packet data fragments are recovered by performing a matrix operation using the inverse of a global transfer matrix such that: GT(t)−1Pin(t).
As a brief overview of constructing a linear network code which, as discussed above, is also referred to as a linear code multicast or LCM, a reduced network is first determined based on the network directed graph such as the example network directed graph 200 shown in FIG. 2. The reduced network is determined by identifying “cuts” separating the source devices from the destination devices. More specifically, a “cut” separating a source device “s” and a destination device “t” is a set of edges of E such that any path from s to t contains an edge from the set. A “minimal cut” separating a source device from a destination device is a cut of the smallest size separating the source device from the destination device. Given these definitions, an example procedure for constructing an LCM given a graph Y=(V, E, s, T) is as follows:                1. Let r=min{mincut(s, t)|t ∈ T}, where mincut(s, t) denotes a minimal cut separating s and t.        2. Determine a reduced network YR=(V, ER, s, T) consisting of r edge disjoint paths from s to each t ∈ T.        3. Select global encoding vectors for each e ∈ ER and construct global transfer matrices Gt for each t ∈ T, such that:                    a. If e influences t on the i-th path, the i-th row of Gt is set to the encoding vector selected for e;            b. Gt is invertible.                        
Given the above example procedures and turning again to the network directed graph 200 of FIG. 2, the goal is to multicast packet data from the source node 1 to the destination nodes 7 and 9. FIG. 3 illustrates an example reduced network graph 300 for the network shown in FIG. 2. In the reduced network graph 300 of FIG. 3, there are three edge-disjoint paths from node 1 to node 7 and twin node 1 to node 9. Thus it is possible to send three packets from node 1 to node 7 in one use of the reduced network, for example during one packet transmission timeslot. Similarly it is possible to send three packets from node 1 to node 9 in one use of the reduced network or during one packet transmission timeslot. However, if three packets are to be multicast from node 1 to node 7 and node 9 during the same interval, then the edge 5→8 becomes a bottleneck.
To resolve the bottleneck, a linear network code can be created based on the procedures described above using a Galois Field of size 256. The following global encoding vectors are therefore generated for the edges:
Lv(1→4)=[88 211 218] Lv(4→7)=[12 197 255];
Lv(1→5)=[56 49 150] Lv(5→7)=[34 34 210];
Lv(1→2)=[164 36 246] Lv(2→5)=[97 42 223];
Lv(5→8)=[106 214 103] Lv(8→7)=[91 158 191];
Lv(5→9)=[199 181 196] Lv(2→6)=[182 229 237];
Lv(6→9)=[65 205 239] Lv(4→5)=[144 153 59];
Lv(8→9)=[232 93 231];
The global transfer matrix 303 for the destination device at node 7 is defined then as:
            G      7        =          [                                    12                                197                                255                                                34                                34                                210                                                91                                158                                191                              ]        ;while the global transfer matrix 309 for the destination device at node 9 is defined as
      G    9    =            [                                    199                                181                                196                                                65                                205                                239                                                232                                93                                231                              ]        .  FIG. 3 also illustrates the traversal of one set of packets 301 through the reduced network. As shown, the transmitted packets 301 can be retrieved from the packets received at each destination devices using the global transfer matrix for that destination device. Therefore as shown in FIG. 3 for node 7, the inverse of the global transfer matrix 305 is multiplied by the received packets 307 to obtain the original transmitted packets 301. For node 9, the inverse of the global transfer matrix 311 is multiplied by the received packets 313 to obtain the original transmitted packets 301.